/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.array;

/**
 * <p>
 * 杨氏矩阵查找 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has
 * the following properties: Integers in each row are sorted from left to right. The first integer
 * of each row is greater than the last integer of the previous row.
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @no 71
 *  2015年5月17日
 */
public class Search2DMatrix {

    public static boolean searchMatrix(int[][] matrix, int target) {
        if(matrix==null) return false;
        int row = matrix.length;
        int col = matrix[0].length;
//        System.out.println("row:"+row+"\tcol:"+col);
        if(row>0 && col>0){
            int i = 0;
            int j = col-1;
            //右上角进行查找
            while(i<row && j>=0){//注意边界条件
                if(matrix[i][j]==target){
                    return true;
                }else if(matrix[i][j]<target){
                    //目标值比它大，则可能在下一行
                    i++;
                }else {//目标值比它小
                    //列数减一
                    j--;
                }
            }
        }
        return false;
    }
    public static void main(String[] args) {
        int ret[][] = {
                                {1,   3,  5,  7},
                                {10, 11, 16, 20},
                                {23, 30, 34, 50},
        };
        System.out.println(searchMatrix(ret,3));
        System.out.println(searchMatrix(ret,8));
        System.out.println(searchMatrix(ret,30));
        System.out.println(searchMatrix(ret,32));
        
        int[][] ret2 = {{1}};
        System.out.println(searchMatrix(ret2, 1));
    }
}
